Synchronous Optical Network (SONET) equipment such as the digital cross-connects (DCC) and add-drop multiplexors (ADM) use circuit switches. In low bandwidth (e.g. OC12) equipments, circuit switches can be implemented using shared memory or a shared bus architecture. However, higher speed circuit switches are often implemented as time-space-time (TST) switches. Time-space-time (TST) switches are well known in the art, and are described in, for example, U.S. Pat. No. 3,736,381 (that is incorporated by reference herein in its entirety) entitled “Time Division Switching System” granted to Johnson et al on May 29, 1973.
One such prior art TST switch 100 (shown in FIG. 1A) is implemented internally by an M×M space switch 102 with one of time switches 101A–101M (wherein A≦I≦M, M being the total number of input time switches) connected to each of its input ports and one of time switches 103A–103M connected at each of its output ports. The value of M depends on the number of streams of information that are to be handled by switch 100, e.g. the value of M may be 32, in which case the space switch may be a 32×32 crossbar.
Time switch 101I receives a stream of information (such as SONET or SDH frames), and rearranges portions of the information before supplying the information to the input port of space switch 102. A control matrix (not shown) for time switch 101I consists of a one-dimensional matrix of size N, where a permutation of the numbers 1, 2 . . . N is stored. The value of N depends on the granularity at which switching is to be done and the line rate, e.g. for an OC-48 line rate and a granularity of STS-1, the value of N would be 48. A value “j” in the ith position in the control matrix means that information received in the ith time slot is switched to the jth slot position.
Another control matrix (also not shown) of space switch 102 consists of a two-dimensional M×N matrix, where a value i in the (j,k)th location means that input port i is to be connected to output port j during time slot k. Such a single connection between a single input port to a single output port is commonly referred to as a unicast connection.
A multicast connection from input port i to multiple output ports w and p during time slot k may be set up by setting both the (w,k)th and (p,k)th locations to value i. If bandwidth more than a single time slot is required then multiple time slots may need to be used in the space switch. The term “connection” refers to a single time slot connection, and as just noted, m time slots may sometimes be required to set up high bandwidth connections between specified input-output ports. In such a case, m single time slot connections are made.
To set up a single time slot connection (hereinafter simply “connection”), logic (that is not shown, but located in TST switch 100) first determines which time slot tS in space switch 102 is to be used for the connection. Once time slot tS is determined, then a control matrix of the appropriate input time switch 101I is set to map the connection from its incoming time slot to slot tS and the appropriate output time switch 103J is set to map from slot tS to the desired outgoing time slot.
If the time slot tS that is determined for the new connection is currently in use by an existing connection, then that existing connection may be moved to different time slot in space switch 102, to make room for the new connection. For more information on such rearrangement, see, for example, U.S. Pat. No. 5,889,775 (incorporated by reference herein in its entirety) granted to Sawicz et al. on Mar. 30, 1999, and U.S. Pat. No. 5,987,027 (that is incorporated by reference herein in its entirety) granted to Park, et al. on Nov. 16, 1999. To rearrange connections in a hitless fashion, new values may be written to a standby control matrix (not shown) and the switch is instructed to use the standby control matrix at the beginning of the next time slot, e.g. at the next frame boundary.
A TST switch (FIG. 1A) with N time slots and M switch ports is equivalent to a Clos network C (m, n, r) illustrated in FIG. 1B, with m=N,n=N and r=M. Clos networks (FIG. 1B) are well known, and are described by, for example, C. Clos in an article entitled “A Study of Non-blocking Switching Networks”, The Bell Systems Technical Journal, 32:406–424, March 1953. See also the descriptions by V. E. Benes in a book entitled “On Rearrangeable Three-stage Connecting Networks”, The Bell Systems Technical Journal, 41(5):1481–1492, September 1962, by V. E. Benes in another article entitled “Mathematical Theory of Connecting Networks and Telephone Traffic,” Academic Press, 1965.
If a demultiplexor is added to each of input ports and a multiplexor is added to each of the output ports of a Clos network (FIG. 1B), then functionally, the resulting network is equivalent to a TST switch (FIG. 1A). Hence, by Slepian-Duguid's theorem (which states that a Clos network C(n; m; r) is rearrangeably nonblocking if m≧n.), the TST switch is rearrangeably nonblocking. A rearrangeably nonblocking switch adds connections by performing rearrangement of the time slots of existing connections, if necessary.
On the other hand, a switch is strictly nonblocking if a new connection can be added as long as there is a free time slot at the input and output ports. To make a TST switch strictly nonblocking, it would be necessary to increase the speed of the space switch by two, or reduce the traffic load by half. Specifically, a Clos network C(n,m,r) is nonblocking if m≧2n−1. Therefore, if the number of time slots handled by the space switch is 2N or if only half of the N time slots at each input port is used, then the TST switch is nonblocking.
Routing methods that permit a CLOS network to handle both point-to-point and broadcast connections are described in, for example, U.S. Pat. Nos. 5,450,074 and 5,276,425 both of which are incorporated by reference herein in their entirety. See also an article entitled “Nonblocking Broadcast Switching Networks,” by Yang, Y., JSSE Transactions on Computers, Vol. 40, No. 9, September 1991, pp. 1005–1015 that is also incorporated by reference herein in its entirety.
When all connections are unicast, then Paull's rearrangement algorithm can be used when adding new connections to a communication switch. Paull's algorithm is described in detail in an article entitled “Reswitching of Connection Networks” by M. C. Paull, The Bell Systems Technical Journal, 41(3):833–855, May 1962, and this article is incorporated by reference herein in its entirety.
Depending on the application, a single connection that uses multiple input ports and multiple output ports (MIMO) may need to be set up through the switch. Such connections cannot be rearranged using Paull's algorithm, because Paull's algorithm can only handle unicast connections.